#include <queue>
#include <vector>
using namespace std;

int orangesRotting(vector<vector<int>> &grid) {
  queue<pair<int, int>> q;
  int fresh = 0, time = 0;
  // 统计新鲜的橘子
  for (int row = 0; row < grid.size(); row++) {
    for (int col = 0; col < grid[0].size(); col++) {
      if (grid[row][col] == 1) {
        fresh++;
      } else if (grid[row][col] == 2) {
        q.push({row, col});
      }
    }
  }
  // 模拟腐烂
  while (!q.empty() && fresh > 0) {
    int q_len = q.size();
    for (int i = 0; i < q_len; i++) {
      auto cur = q.front();
      q.pop();
      // 广度优先搜索
      if (cur.first + 1 < grid.size() && grid[cur.first + 1][cur.second] == 1) {
        grid[cur.first + 1][cur.second] = 2;
        fresh--;
        q.push({cur.first + 1, cur.second});
      }
      if (cur.first - 1 >= 0 && grid[cur.first - 1][cur.second] == 1) {
        grid[cur.first - 1][cur.second] = 2;
        fresh--;
        q.push({cur.first - 1, cur.second});
      }
      if (cur.second - 1 >= 0 && grid[cur.first][cur.second - 1] == 1) {
        grid[cur.first][cur.second - 1] = 2;
        fresh--;
        q.push({cur.first, cur.second - 1});
      }
      if (cur.second + 1 < grid[0].size() &&
          grid[cur.first][cur.second + 1] == 1) {
        grid[cur.first][cur.second + 1] = 2;
        fresh--;
        q.push({cur.first, cur.second + 1});
      }
    }
    time++;
  }
  if (fresh != 0) {
    return -1;
  }
  return time;
}